Кластерный анализ

Вы сможете

  • Выбирать подходящий метод аггрегации (алгоритм кластеризации)
  • Строить дендрограммы
  • Оценивать качество кластеризации (Кофенетическая корреляция, поддержка ветвей)
  • Рассчитывать оптимальное число кластеров
  • Сопоставлять дендрограммы, полученные разными способами, при помощи танглграмм

Кластерный анализ

Какие бывают методы построения деревьев?

Методы класстеризации на основании расстояний (о них сегодня)

  • Метод ближайшего соседа
  • Метод отдаленного соседа
  • Метод среднегруппового расстояния
  • Метод Варда
  • и т.д. и т.п.

Методы кластеризации на основании признаков

  • Метод максимальной бережливости
  • Метод максимального правдоподобия

И это еще далеко не все

Методы класстеризации на основании расстояний

Этапы кластеризации

От чего зависит результат кластеризации

Результат кластеризации зависит от

  • коэффициента сходства-различия
  • от алгоритма кластеризации

Методы кластеризации

Метод ближайшего соседа

= nearest neighbour = single linkage

  • к кластеру присоединяется ближайший к нему кластер/объект
  • кластеры объединяются в один на расстоянии, которое равно расстоянию между ближайшими объектами этих кластеров

Особенности:

  • Может быть сложно интерпретировать, если нужны группы
  • объекты на дендрограмме часто не образуют четко разделенных групп
  • часто получаются цепочки кластеров (объекты присоединяются как бы по-одному)
  • Хорош для выявления градиентов

Метод отдаленного соседа

= furthest neighbour = complete linkage

  • к кластеру присоединяется отдаленный кластер/объект
  • кластеры объединяются в один на расстоянии, которое равно расстоянию между самыми отдаленными объектами этих кластеров (следствие - чем более крупная группа, тем сложнее к ней присоединиться)

Особенности:

  • На дендрограмме образуется много отдельных некрупных групп
  • Хорош для поиска дискретных групп в данных

Метод невзвешенного попарного среднего

= UPGMA = Unweighted Pair Group Method with Arithmetic mean

  • кластеры объединяются в один на расстоянии, которое равно среднему значению всех возможных расстояний между объектами из разных кластеров.

Особенности:

  • UPGMA и WUPGMС иногда могут приводить к инверсиям на дендрограммах
из Borcard et al., 2011

Метод Варда

= Ward's Minimum Variance Clustering

  • объекты объединяются в кластеры так, чтобы внутригрупповая дисперсия расстояний была минимальной

Особенности:

  • метод годится и для неевклидовых расстояний несмотря на то, что внутригрупповая дисперсия расстояний рассчитывается так, как будто это евклидовы расстояния

Кластерный анализ в R

Пример: поссумы

Морфометрия самок поссумов

library(DAAG)
## Loading required package: lattice
data(fossum)
# создадим "говорящие" имена строк 
rownames(fossum) <- paste(fossum$Pop, rownames(fossum), sep = "_")
fossumc <- fossum[complete.cases(fossum), 5:14]

Давайте построим деревья при помощи нескольких алгоритмов кластеризации (по стандартизованным данным, с использованием Евклидова расстояния) и сравним их.

d <- dist(x = scale(fossumc), method = "euclidean")

Метод ближайшего соседа в R

hc_single <- hclust(d, method = "single")
library(ape)
ph_single <- as.phylo(hc_single)
plot(ph_single, type = "phylogram", cex = 0.7)
axisPhylo()

Метод отдаленного соседа в R

ph_compl <- as.phylo(hclust(d, method = "complete"))
plot(ph_compl, type = "phylogram", cex = 0.7)
axisPhylo()

Метод невзвешенного попарного среднего в R

ph_avg <- as.phylo(hclust(d, method = "average"))
plot(ph_avg, type = "phylogram", cex = 0.7)
axisPhylo()

Метод Варда в R

ph_w2<- as.phylo(hclust(d, method = "ward.D2"))
plot(ph_w2, type = "phylogram", cex = 0.7)
axisPhylo()

Cравнение и интерпретация результатов кластеризации

Кофенетическая корреляция

Кофенетическое расстояние - расстояние между объектами на дендрограмме

Кофенетическую корреляцию можно рассчитать как пирсоновскую корреляцию (обычную) между матрицами исходных и кофенетических расстояний между всеми парами объектов

Метод, который дает наибольшую кофенетическую корреляцию дает кластеры лучше всего отражающие исходные данные

Кофенетическая корреляция в R

c_single <- cophenetic(ph_single)
c_compl <- cophenetic(ph_compl)
c_avg <- cophenetic(ph_avg)
c_w2 <- cophenetic(ph_w2)

cor(d, as.dist(c_single))
## [1] 0.679
cor(d, as.dist(c_compl))
## [1] 0.524
cor(d, as.dist(c_avg)) # лучше всех отражает структуру данных
## [1] 0.742
cor(d, as.dist(c_w2))
## [1] 0.541

На каком уровне нужно делить дендрограмму на кластеры?

  • Можно субъективно, на любом выбранном уровне. Главное, чтобы кластеры были осмысленными и интерпретируемыми.
  • Можно выбрать, глядя на распределение расстояний ветвления
  • Можно оценить вероятность разделения на кластеры при помощи бутстрепа

Бутстреп

library(pvclust)
# итераций должно быть 1000 и больше
# здесь мало для скорости
set.seed(42)
cl_boot <- pvclust(scale(t(fossumc)), method.hclust = "average", nboot = 50, method.dist = "euclidean")
## Bootstrap (r = 0.5)... Done.
## Bootstrap (r = 0.6)... Done.
## Bootstrap (r = 0.7)... Done.
## Bootstrap (r = 0.8)... Done.
## Bootstrap (r = 0.9)... Done.
## Bootstrap (r = 1.0)... Done.
## Bootstrap (r = 1.1)... Done.
## Bootstrap (r = 1.2)... Done.
## Bootstrap (r = 1.3)... Done.
## Bootstrap (r = 1.4)... Done.

plot(cl_boot)
pvrect(cl_boot)

И небольшая демонстрация - дерево по генетическим данным

webpage <-"http://evolution.genetics.washington.edu/book/primates.dna"
primates.dna <- read.dna(webpage)
d_pri <- dist.dna(primates.dna)
hc_pri <- hclust(d_pri, method = "average")
ph_pri <- as.phylo(hc_pri)
plot(ph_pri)
axisPhylo()

Take home messages

Дополнительные ресурсы

  • Borcard, D., Gillet, F., Legendre, P., 2011. Numerical ecology with R. Springer.
  • Legendre, P., Legendre, L., 2012. Numerical ecology. Elsevier.
  • Quinn, G.G.P., Keough, M.J., 2002. Experimental design and data analysis for biologists. Cambridge University Press.